#include <defs.h>
#include <riscv.h>
#include <stdio.h>
#include <string.h>
#include <swap.h>
#include <swap_fifo.h>
#include <list.h>

/* [wikipedia] 最简单的页面置换算法是FIFO算法。先进先出页面置换算法是一种低开销的算法，
 * 操作系统只需进行少量的记录。顾名思义，操作系统通过一个队列跟踪内存中的所有页面，
 * 最近到达的页面在队列的末尾，最早到达的页面在队列的前面。当需要替换页面时，选择队列前面的页面（最旧的页面）。
 * 虽然FIFO简单直观，但在实际应用中表现不佳。因此，它很少以未修改的形式使用。
 * 该算法会出现Belady异常。
 *
 * FIFO PRA的细节
 * (1) 准备：为了实现FIFO PRA，我们应该管理所有可交换页面，以便根据时间顺序将这些页面链接到pra_list_head。
 *     首先，你应该熟悉list.h中的struct list。struct list是一个简单的双向链表实现。
 *     你应该知道如何使用：list_init, list_add(list_add_after), list_add_before, list_del, list_next, list_prev。
 *     另一个技巧是将通用的链表结构转换为特定的结构（如struct page）。
 *     你可以找到一些宏：le2page（在memlayout.h中），（在未来的实验中：le2vma（在vmm.h中），le2proc（在proc.h中）等）。
 */

extern list_entry_t pra_list_head; // 定义一个链表头，用于管理可交换页面

/*
 * (2) _fifo_init_mm: 初始化pra_list_head并让mm->sm_priv指向pra_list_head的地址。
 *     现在，从内存控制结构mm_struct中，我们可以访问FIFO PRA。
 */
static int
_fifo_init_mm(struct mm_struct *mm)
{     
     list_init(&pra_list_head); // 初始化pra_list_head链表
     mm->sm_priv = &pra_list_head; // 将mm->sm_priv指向pra_list_head
     //cprintf(" mm->sm_priv %x in fifo_init_mm\n",mm->sm_priv); // 打印调试信息
     return 0;
}

/*
 * (3) _fifo_map_swappable: 根据FIFO PRA，我们应该将最近到达的页面链接到pra_list_head队列的末尾。
 */
static int
_fifo_map_swappable(struct mm_struct *mm, uintptr_t addr, struct Page *page, int swap_in)
{
    list_entry_t *head = (list_entry_t*) mm->sm_priv; // 获取链表头
    list_entry_t *entry = &(page->pra_page_link); // 获取页面的链表节点

    assert(entry != NULL && head != NULL); // 确保entry和head不为空
    // 记录页面访问情况

    //(1) 将最近到达的页面链接到pra_list_head队列的末尾。
    list_add(head, entry); // 将entry添加到head链表中
    return 0;
}

/*
 * (4) _fifo_swap_out_victim: 根据FIFO PRA，我们应该从pra_list_head队列中取消链接最早到达的页面，
 *                            然后将该页面的地址设置到ptr_page。
 */
static int
_fifo_swap_out_victim(struct mm_struct *mm, struct Page ** ptr_page, int in_tick)
{
     list_entry_t *head = (list_entry_t*) mm->sm_priv; // 获取链表头
     assert(head != NULL); // 确保head不为空
     assert(in_tick == 0); // 确保in_tick为0
     /* 选择受害者 */
     //(1) 从pra_list_head队列中取消链接最早到达的页面
     //(2) 将该页面的地址设置到ptr_page
    list_entry_t* entry = list_prev(head); // 获取链表中最早到达的页面
    if (entry != head) {
        list_del(entry); // 从链表中删除entry
        *ptr_page = le2page(entry, pra_page_link); // 将entry转换为页面并赋值给ptr_page
    } else {
        *ptr_page = NULL; // 如果没有页面可删除，设置ptr_page为NULL
    }
    return 0;
}

static int
_fifo_check_swap(void) {
    cprintf("write Virt Page c in fifo_check_swap\n");
    *(unsigned char *)0x3000 = 0x0c; // 写入虚拟页面c
    assert(pgfault_num == 4); // 确保页故障数为4
    cprintf("write Virt Page a in fifo_check_swap\n");
    *(unsigned char *)0x1000 = 0x0a; // 写入虚拟页面a
    assert(pgfault_num == 4); // 确保页故障数为4
    cprintf("write Virt Page d in fifo_check_swap\n");
    *(unsigned char *)0x4000 = 0x0d; // 写入虚拟页面d
    assert(pgfault_num == 4); // 确保页故障数为4
    cprintf("write Virt Page b in fifo_check_swap\n");
    *(unsigned char *)0x2000 = 0x0b; // 写入虚拟页面b
    assert(pgfault_num == 4); // 确保页故障数为4
    cprintf("write Virt Page e in fifo_check_swap\n");
    *(unsigned char *)0x5000 = 0x0e; // 写入虚拟页面e
    assert(pgfault_num == 5); // 确保页故障数为5
    cprintf("write Virt Page b in fifo_check_swap\n");
    *(unsigned char *)0x2000 = 0x0b; // 写入虚拟页面b
    assert(pgfault_num == 5); // 确保页故障数为5
    cprintf("write Virt Page a in fifo_check_swap\n");
    *(unsigned char *)0x1000 = 0x0a; // 写入虚拟页面a
    assert(pgfault_num == 6); // 确保页故障数为6
    cprintf("write Virt Page b in fifo_check_swap\n");
    *(unsigned char *)0x2000 = 0x0b; // 写入虚拟页面b
    assert(pgfault_num == 7); // 确保页故障数为7
    cprintf("write Virt Page c in fifo_check_swap\n");
    *(unsigned char *)0x3000 = 0x0c; // 写入虚拟页面c
    assert(pgfault_num == 8); // 确保页故障数为8
    cprintf("write Virt Page d in fifo_check_swap\n");
    *(unsigned char *)0x4000 = 0x0d; // 写入虚拟页面d
    assert(pgfault_num == 9); // 确保页故障数为9
    cprintf("write Virt Page e in fifo_check_swap\n");
    *(unsigned char *)0x5000 = 0x0e; // 写入虚拟页面e
    assert(pgfault_num == 10); // 确保页故障数为10
    cprintf("write Virt Page a in fifo_check_swap\n");
    assert(*(unsigned char *)0x1000 == 0x0a); // 确保虚拟页面a的值为0x0a
    *(unsigned char *)0x1000 = 0x0a; // 写入虚拟页面a
    assert(pgfault_num == 11); // 确保页故障数为11
    return 0;
}

static int
_fifo_init(void)
{
    return 0; // 初始化函数，返回0
}

static int
_fifo_set_unswappable(struct mm_struct *mm, uintptr_t addr)
{
    return 0; // 设置页面不可交换，返回0
}

static int
_fifo_tick_event(struct mm_struct *mm)
{ 
    return 0; // 时钟事件处理函数，返回0
}

struct swap_manager swap_manager_fifo =
{
     .name            = "fifo swap manager", // 交换管理器名称
     .init            = &_fifo_init, // 初始化函数
     .init_mm         = &_fifo_init_mm, // 初始化内存管理函数
     .tick_event      = &_fifo_tick_event, // 时钟事件处理函数
     .map_swappable   = &_fifo_map_swappable, // 映射可交换页面函数
     .set_unswappable = &_fifo_set_unswappable, // 设置页面不可交换函数
     .swap_out_victim = &_fifo_swap_out_victim, // 选择受害者页面并交换出去的函数
     .check_swap      = &_fifo_check_swap, // 检查交换的函数
};